package leetcode_900;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *AmbiguousCoordinates_816 类似构造字符串合法问题
 *describe:用深搜就可以了 因为只需要区分出两个区间 AC 62%
 *2018年10月27日 下午4:46:37
 */
public class AmbiguousCoordinates_816 {
	public List<String> ambiguousCoordinates(String S) {
        List<String> res = new ArrayList<>();
        S = S.substring(1, S.length() - 1);
        for (int i = 1; i < S.length(); i++) {
            List<String> res1 = helper(S.substring(0, i));
            List<String> res2 = helper(S.substring(i));
            if (res1.size() == 0 || res2.size() == 0) continue;
            for (String s1 : res1) {
                for (String s2 : res2) {
                    res.add("(" + s1 + ", " + s2 + ")");
                }
            }
        }
        return res;
    }
    private List<String> helper (String S) {
        List<String> res = new ArrayList();
        if (S.length() == 0) return res;
        if (S.length() == 1 || (S.charAt(0) != '0' && S.charAt(S.length() - 1) == '0')) {
            res.add(S);
            return res;
        }
        if (S.charAt(0) == '0' && S.charAt(S.length() - 1) == '0') return res;
        if (S.charAt(0) == '0') {
            res.add(S.substring(0, 1) + "." + S.substring(1, S.length()));
            return res;
        }
        for (int i = 0; i < S.length() - 1; i++) {
            res.add(S.substring(0, i + 1) + "." + S.substring(i + 1, S.length()));
        }
        res.add(S);
        return res;
    }
}
